package cn.demoncat.util.lang.entity.data;

/**
 * 二叉平衡树（AVL树）
 * 
 * 性质：增删结点时，执行双旋转（保证左右子树的深度差不大于1）
 * 
 * @author 延晓磊
 *
 * @since 2020年7月23日
 */
public class BalancedBianryTree<T extends Comparable<T>> extends SortBinaryTree<T> {

	/**
	 * 删除结点：叶子结点-删除结点，分枝结点-删除子树
	 * 
	 * @param data
	 *            目标数据（删除第一个匹配到的结点）
	 * 
	 * @return 是否删除
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	@Override
	public boolean removes(T data) {
		if (root != null) {
			// 判断根结点
			if (data.compareTo(root.data) == 0) {
				// 删除根结点
				root = null;
				return true;
			} else {
				// 查找结点
				BinaryTreeNode<T> node = search(data);
				if (node != null) {
					if (node.parent.left == node) {
						node.parent.left = null;
					} else {
						node.parent.right = null;
					}
					// 平衡旋转
					rotate(node.parent);
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * 删除结点：叶子结点-删除结点，分枝结点-提升子结点
	 * 
	 * @param data
	 *            目标数据（删除第一个匹配到的结点）
	 * 
	 * @return 是否删除
	 * 
	 * @author 延晓磊
	 * @return
	 *
	 * @since 2020年7月23日
	 */
	@Override
	public boolean remove(T data) {
		return remove(data, this::rotate);
	}

	/**
	 * 添加结点
	 * 
	 * @param parent
	 *            父结点
	 * @param node
	 *            结点
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月22日
	 */
	@Override
	protected void add(BinaryTreeNode<T> parent, BinaryTreeNode<T> node) {
		// 添加结点
		if (node.data.compareTo(parent.data) < 0) {
			// node < parent = 左子树
			if (parent.left == null) {
				parent.left = node;
			} else {
				add(parent.left, node);
			}
		} else {
			// node >= parent = 右子树
			if (parent.right == null) {
				parent.right = node;
			} else {
				add(parent.right, node);
			}
		}
		// 平衡旋转
		parent.rotate();
	}

	/**
	 * 平衡旋转（回朔至根结点）
	 * 
	 * @param node
	 *            操作结点（添加、删除子结点）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月23日
	 */
	private void rotate(BinaryTreeNode<T> node) {
		// 旋转结点：删除子结点，会导致结点不平衡
		node.rotate();
		// 旋转祖先结点：添加子结点，会导致父结点不平衡；平衡结点，会导致父结点不平衡
		findParents(node, BinaryTreeNode::rotate);
	}

}
